/*
day263
2020.5.17
*/

#include<iostream>
#include<string>
#include<vector>
using namespace std; 

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
	struct Node{
		int val;
		int depth;
		Node() : val(0),depth(0){}
	};
	
public:
    TreeNode* recoverFromPreorder(string S) {
		vector<Node> vec=split(S);
		int index=0;
		return help(vec,0,index);
    }
    
    TreeNode* help(vector<Node> &vec,int depth,int &index)
    {
    	if(index>=vec.size() || vec[index].depth!=depth  )
    	{
    		return nullptr;
		}
		
		TreeNode *root=new TreeNode (vec[index].val);
		index++;
		root->left=help(vec,depth+1,index);
		root->right=help(vec,depth+1,index);
		
		return root;
	}
    
    
    vector<Node> split(string S)
    {
    	vector<Node> vec;
    	Node node;
    	
    	int cur=0;
    	
    	for(int i=0;i<S.size();)
    	{
    		if(S[i]=='-')
    		{
    			cur++;
    			i++;
			}
			else
			{
				int begin=i;
				while(i<S.size() && S[i]!='-')
				{
					i++;
				}
				
				string tem=S.substr(begin,i-begin);
				node.val=stoi(tem);
				node.depth=cur;
				cur=0;
				vec.push_back(node);
			}
		}
		return vec;
	}
	
	
	int stoi(string str)
	{
		int sum=0;
		for(int i=0;i<str.size();++i)
		{
			int cur=str[i]-'0';
			sum*=10;
			sum+=cur;
		}
		return sum;
	}
};

int main()
{
	string str="1-2--3--4-5--6--7";
	Solution s;
	s.recoverFromPreorder(str);
	return 0;
}
